import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
public class Grafo {
        private List<No> nos = new ArrayList<No>();
        private List<Aresta> arestas = new ArrayList<Aresta>();

        public void setArestas(List<Aresta> arestas_novas){
                
                arestas.addAll(arestas_novas);
        }

        public List<Aresta> getArestas() {

                return arestas;

        }

        public void setNos(List<No> Nos) {
                
                this.nos.addAll(Nos);
        }

        public List<No> getNos() {
                
                return this.nos;
        }
        
        public void ordenarLista(List<No> lista){
                
                for (int i=lista.size()-2;i>=0;i--){
                        
                        for (int j=0;j<i;j++){
                                
                                if (lista.get(j).getDistancia() > lista.get(j+1).getDistancia()){
                                        
                                        Collections.swap(lista, j, j+1);
                                }
                        }
                }
        }
        

        	
        
        public List<No> menorCaminho(No v1, No v2){
            
            List<No> menorCaminho = new ArrayList<No>();
            No caminho = new No ("caminho");
            No novo = new No ("atual");
            No vizinho = new No ("vizinho");
            List<No> fronteira = new ArrayList<No>();
            int NosNaoVisitados = this.nos.size();
            
            novo = v1;
            fronteira.add(novo);
            menorCaminho.add(novo);
            
            
            for (int i=0;i< this.nos.size();i++){
                    
                    if (this.nos.get(i).equals(v1)){
                            
                            this.nos.get(i).setDistancia(0);
                    } else{
                            
                            this.nos.get(i).setDistancia(9999);
                            
                    }
                    
            }
            
            while (NosNaoVisitados != 0){
                    
                    novo = fronteira.get(0);
                    
                    for (int i=0; i<novo.getArestas().size();i++){
                            
                            
                            if (novo.getArestas().get(i).getNos().get(0).equals(novo)){
                                    
                                    vizinho = novo.getArestas().get(i).getNos().get(1);
                            } else {
                                    
                                    vizinho = novo.getArestas().get(i).getNos().get(0);
                            }
                            
                            vizinho.setPai(novo);
                            
                            if (vizinho.getDistancia() > (novo.getDistancia() + novo.getArestas().get(i).getPeso())){
                                    
                                    vizinho.setDistancia(novo.getDistancia() + novo.getArestas().get(i).getPeso());
                                    if (vizinho.equals(v2)){
                                            menorCaminho.clear();
                                            caminho = vizinho;
                                            while (!caminho.equals(novo)){
                                                    
                                                    menorCaminho.add(caminho);
                                                    caminho = caminho.getPai();
                                                    
                                            }
                                            this.ordenarLista(menorCaminho);
                                    }
                            }
                            fronteira.add(vizinho);
                            
                    }
                    
                    novo.visitar();
                    NosNaoVisitados--;
                    fronteira.remove(novo);
                    this.ordenarLista(fronteira);
            
            }
                            
            return menorCaminho;
    }   
}